package alo.p7.work;

import alo.p7.Heap;

/**
 * @ClassName FindKthLargesEle
 * @Description 给出最大堆的找到的第K个最小元素的算法
 * @Author Fanxc
 * @DATE 2021/3/10 15:20
 * @Version 1.0
 */
public class FindKthLargesEle {
    //HOrig为原始数据堆，HAux为辅助堆
    Heap HOrig,HAux;
    int findKthLargesEle(int k){
        if (k<=0)return Integer.MAX_VALUE;
        int heapElement=-1;
        //计数的同时，进行孩子索引的计算
        HAux.Insert(HOrig.DeleteMax());
        for (int count=0; count < k; count++) {
            heapElement= HAux.DeleteMax();
            //把左右孩子加入堆中
            HAux.Insert(HOrig.LeftChild(key(count)));
            HAux.Insert(HOrig.RightChild(key2(count)));
        }
        return heapElement;

//        while (true){
//            heapElement= HAux.DeleteMax();
//            if (++count==k-1){
//                return heapElement;
//            }else {
//                HAux.Insert(HOrig.LeftChild(key(count)));
//                HAux.Insert(HOrig.RightChild(key2(count)));
//            }
//        }
    }
    //计算左孩子的索引
    int key(int count){
        int key=0;
        for (int i = 0; i < count; i++) {
            key=key*2+1;
        }
        return key;
    }
    //计算右孩子的索引
    int key2(int count){
        int key=0;
        for (int i = 0; i < count; i++) {
            key=key*2+1;
        }
        return key;
    }
}
